package demo2;


public class TestDemo1 {

    //给你一组面值,每个面值都不相同,每个面值有无限张,求组成aim的最小张数
    //[1,5]  aim: 20
    public static int ways1(int[] arr,int aim){
        return process(arr,0,aim);
    }
    //从arr[index.....]从index位置开始组成的钱到达rest->剩余钱数
    public static int process(int[] arr,int index,int rest){
        if(index==arr.length) return rest == 0 ? 0 : Integer.MAX_VALUE;
        int ans = Integer.MAX_VALUE;
        for(int zhang = 0 ; zhang*arr[index]<=rest;zhang++){
            int next = process(arr,index+1,rest - zhang * arr[index]);
            if(next!=Integer.MAX_VALUE){
                ans = Math.min(ans,next+zhang);
            }
        }
        return ans;
    }

    //========================改成动态规划===================
    //有枚举行为的
    public static int dp3(int[] arr,int aim){
        int N = arr.length;
        int[][] dp = new int[N+1][aim+1];
        dp[N][0] = 0;
        for(int i = 1;i<=aim;++i){
            dp[N][i] = Integer.MAX_VALUE;
        }

        for(int index = N-1;index>=0;--index){
            for(int rest = 0;rest<=aim;++rest){
                int ans = Integer.MAX_VALUE;
                for(int zhang = 0 ; zhang*arr[index]<=rest;zhang++){
                    int next = dp[index+1][rest - zhang * arr[index]];
                    if(next!=Integer.MAX_VALUE){
                        ans = Math.min(ans,next+zhang);
                    }
                    dp[index][rest] = ans;
                }
            }
        }
        return dp[0][aim];
    }

    //改成斜率优化版本的动态规划
    public static int dp4(int[] arr,int aim){
        int N = arr.length;
        int[][] dp = new int[N+1][aim+1];
        dp[N][0] = 0;
        for(int i =1;i<=aim;++i){
            dp[N][i] = Integer.MAX_VALUE;
        }
        for(int index = N-1;index>=0;index--){
            for(int rest =0;rest<=aim;++rest){
                dp[index][rest] = dp[index+1][rest];
                if(rest-arr[index]>=0&&
                dp[index][rest-arr[index]]!=Integer.MAX_VALUE){
                    dp[index][rest] = Math.min(dp[index][rest],dp[index][rest-arr[index]]+1);
                }
            }
        }
        return dp[0][aim];
    }

    public static void main(String[] args) {
        int[] arr = {1,5,10,56,30,96,2};
        int aim = 50;
        System.out.println(ways1(arr, aim));
        System.out.println(dp3(arr, aim));
        System.out.println(dp4(arr, aim));

    }

}
